package leetcode.daily;

import java.util.*;

public class a_20201224 {


    /**
     * 1203. 项目管理
     * 公司共有 n 个项目和  m 个小组，每个项目要不没有归属，要不就由其中的一个小组负责。
     *
     * 我们用 group[i] 代表第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）
     *
     * 请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
     *
     * 同一小组的项目，排序后在列表中彼此相邻。
     * 项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
     * 结果要求：
     *
     * 如果存在多个解决方案，只需要返回其中任意一个即可。
     *
     * 如果没有合适的解决方案，就请返回一个 空列表。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
     * 输出：[6,3,4,1,5,2,0,7]
     * 示例 2：
     *
     * 输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
     * 输出：[]
     * 解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。
     *
     *
     * 提示：
     *
     * 1 <= m <= n <= 3*10^4
     * group.length == beforeItems.length == n
     * -1 <= group[i] <= m-1
     * 0 <= beforeItems[i].length <= n-1
     * 0 <= beforeItems[i][j] <= n-1
     * i != beforeItems[i][j]
     */
    static class Solution {
        /* 基类，用于拓扑排序 */
        private static class Sortable {
            public int ID;
            public Set<Sortable> next;

            public Sortable(int ID) {
                this.ID = ID;
                this.next = new HashSet<>(); // 后继节点
            }
        }

        /* 项目类 */
        private static class Item extends Sortable {

            public Item(int ID) {
                super(ID);
            }
        }

        /* 项目组类 */
        private static class Group extends Sortable {
            public Map<Integer, Item> items = new HashMap<>();              // 项目组负责的项目
            public Map<Integer, Integer> itemInDegrees = new HashMap<>();   // 各项目节点的入度

            public Group(int ID) {
                super(ID);
            }
        }

        /* 拓扑排序结果类 */
        private static class SortResult {
            public boolean success;
            public List<Sortable> result;

            public SortResult(boolean success, List<Sortable> result) {
                this.success = success;
                this.result = result;
            }
        }

        private Map<Integer, Group> groups = new HashMap<>();           // 以项目组为节点构成的图
        private Map<Integer, Integer> groupInDegrees = new HashMap<>(); // 项目组节点的入度，方便拓扑排序

        public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
            initialize(n, m, group, beforeItems);
            SortResult sortedGroups = topologicalSort(groups, groupInDegrees);  // 首先进行项目组的拓扑排序
            if (!sortedGroups.success) return new int[0];
            int[] ans = new int[n];
            int curr = 0;
            for (Sortable s1 : sortedGroups.result) {                           // 再对每组中的项目进行拓扑排序
                Group g = (Group) s1;
                SortResult sortedItems = topologicalSort(g.items, g.itemInDegrees);
                if (!sortedItems.success) return new int[0];
                for (Sortable s2 : sortedItems.result) {
                    Item item = (Item) s2;
                    ans[curr++] = item.ID;
                }
            }
            return ans;
        }

        /**
         * 拓扑排序代码
         *
         * 我们具体的代码思想为：
         *
         * 新建node类，包含节点数值和它的指向(这里直接用list集合替代链表了)
         * 一个数组包含node(这里默认编号较集中)。初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
         * 扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。
         * 当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为0，那么就将它加入栈(队列)。
         * 重复上述操作，直到栈为空。
         * 这里主要是利用栈或者队列储存入度只为0的节点，只需要初次扫描表将入度为0的放入栈(队列)中。
         *
         * 这里你或许会问为什么。
         * 因为节点之间是有相关性的，一个节点若想入度为零，那么它的父节点(指向节点)肯定在它为0前入度为0，拆除关联箭头。从父节点角度，它的这次拆除联系，可能导致被指向的入读为0，也可能不为0(还有其他节点指向儿子)
         *
         *
         * @param graph     待排序的图
         * @param inDegrees 图中各节点的入度
         * @return          排序结果
         */
        private SortResult topologicalSort(Map<Integer, ? extends Sortable> graph, Map<Integer, Integer> inDegrees) {
            List<Sortable> list = new ArrayList<>();
            Queue<Sortable> queue = new LinkedList<>();
            for (Map.Entry<Integer, Integer> entry : inDegrees.entrySet())  {
                if (entry.getValue() == 0)
                    queue.offer(graph.get(entry.getKey()));
            }
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Sortable sortable = queue.poll();
                    for (Sortable s : sortable.next) {
                        int inDegree = inDegrees.get(s.ID);
                        if (inDegree == 1) queue.offer(s);
                        inDegrees.put(s.ID, inDegree - 1);
                    }
                    list.add(sortable);
                }
            }
            boolean success = list.size() == graph.size();
            return new SortResult(success, list);
        }

        /* 成员变量的预处理 */
        private void initialize(int n, int m, int[] group, List<List<Integer>> beforeItems) {
            int t = 0;
            Item[] items = new Item[n];
            for (int i = 0; i < n; i++) {
                items[i] = new Item(i);
                if (group[i] == -1)
                    group[i] = (m + t++);

            }
            for (int i = 0; i < m + t; i++) {
                groups.put(i, new Group(i));
                groupInDegrees.put(i, 0);
            }
            for (int i = 0; i < n; i++) {
                Group currentGroup = groups.get(group[i]);
                currentGroup.items.put(i, items[i]);
                currentGroup.itemInDegrees.put(i, 0);
            }
            for (int i = 0; i < n; i++) {
                Group currentGroup = groups.get(group[i]);
                for (int j : beforeItems.get(i)) {
                    if (group[i] == group[j]) {
                        items[j].next.add(items[i]);
                        currentGroup.itemInDegrees.compute(i, (k, v) -> v + 1);
                    } else {
                        groups.get(group[j]).next.add(currentGroup);
                    }
                }
            }
            for (Map.Entry<Integer, Group> entry : groups.entrySet()) {
                Group g = entry.getValue();
                for (Sortable next : g.next) {
                    groupInDegrees.compute(next.ID, (k, v) -> v + 1);
                }
            }
        }
    }
}
